链表增加结点
链表增加结点
有三种情况:
- add(item)链表头部增加结点
- append(item)尾部增加结点
- insert(pos, item)指定位置增加结点
add(item)链表头部增加结点
步骤
- 新结点的next指向原始的头结点
new_node.next = head
- 然后让head指向新结点
head = new_node
# 单链表的实现
class SingleLinkList(object):
......
# 头部增加结点
# add()
def add(self, item):
# 新结点存储新数据
node = SingleNode(item)
node.next = self.head
self.head = node
append(item)尾部增加结点
步骤
尾结点.next = 新结点
如何找到尾结点:
cur = head
while cur.next is not None:
cur = cur.next
# 单链表的实现
class SingleLinkList(object):
def __init__(self, node=None):
# head: 首结点
self.head = node
# 判断链表是否为空
def is_empty(self):
if self.head is None:
return True
else:
return False
# 获取链表长度
......
# 遍历链表
......
# 头部增加结点
......
# 尾部增加结点
# append()
def append(self, item):
# 新结点存储数据
node = SingleNode(item)
# 判断是否为空链表
if self.is_empty():
self.head = node
else:
cur = self.head
# 找到尾结点
while cur.next is not None:
cur = cur.next
cur.next = node
在指定位置增加结点
- 在pos -1, 与 pos之间新增结点,需要注意
- 如果pos为0即负数,那么就直接在头部新增结点
- 如果pos大于等于链表长度,则直接在尾部新增结点
# 单链表的实现
class SingleLinkList(object):
def __init__(self, node=None):
# head: 首结点
self.head = node
# 判断链表是否为空
def is_empty(self):
if self.head is None:
return True
else:
return False
# 获取链表长度
def length(self):
# 游标记录当前所在的位置
cur = self.head
# 记录链表的长度
count = 0
while cur is not None:
cur = cur.next
count += 1
return count
# 遍历链表
......
# 头部增加结点
# add()
......
# 尾部增加结点
# append()
......
# 指定位置增加结点
# insert(pos, item)
def insert(self, pos, item):
# 头部增加新结点
if pos <= 0:
self.add(item)
elif pos >= self.length():
# 尾部添加结点
self.append(item)
else:
# 游标
cur = self.head
# 计数
count = 0
# 新结点
node = SingleNode(item)
# 找到插入位置的前一个结点
while count < pos - 1:
cur = cur.next
count += 1
# 完成插入新结点
node.next = cur.next
cur.next = node